import org.junit.Test;

public class leetcode {
    @Test
    public void test(){
        String b = "fdasaccaccaqsd";

        String a ="accaq";
        int[] left = left(a);
        for (int i : left) {
            System.out.println(i);
        }
        int le=0;
        for(int i =0;i< b.length();i++){
            do {
                if(b.charAt(i)==a.charAt(le)){
                    i++;
                    le++;
                    if(le==a.length()){
                        System.out.println(i-le);
                        return;
                    }
                }else if(le==0){
                    break;
                }else {
                    if(left[le-1]==-1) break;
                    le=left[le-1];
                }
            }while (le!=0);
        }
        System.out.println("======");
    }
    public static int[] left(String a){
        int[] lrs = new int[a.length()];
        lrs[0] = -1; //-1表示开头的字符
        int le=0;
        for (int i = 1; i < lrs.length; i++) {
            while (le>=0 && le<i){
                if(a.charAt(le)==a.charAt(i)){
                    lrs[i]=++le;
                    break;
                }else {
                    if(le==0) break;
                    le=lrs[le-1];
                }
            }
        }
        return lrs;
    }
}

